TNotes.leetcode

Appearance

0933. 最近的请求次数【简单】

0933. 最近的请求次数【简单】 ​

1. 📝 题目描述 ​

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类：

  • RecentCounter() 初始化计数器，请求数为 0。
  • int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。

保证每次对 ping 的调用都使用比之前更大的 t 值。

示例 1：

输入：
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]

输出：
[null, 1, 2, 3, 3]

解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100);   // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001);  // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3

提示：

  • 1 <= t <= 10^9
  • 保证每次对 ping 调用所使用的 t 值都严格递增
  • 至多调用 ping 方法 10^4 次

2. 🎯 s.1 - 队列（头指针优化） ​

js
// 使用队列 + 头指针，避免 O(n) 的 shift 开销
var RecentCounter = function () {
  this.q = []
  this.head = 0
}

/**
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function (t) {
  this.q.push(t)
  const lower = t - 3000
  // 前移头指针，跳过过期请求
  while (this.head < this.q.length && this.q[this.head] < lower) this.head++
  // 可选压缩：防止 head 过大导致数组增长
  if (this.head > 1024 && this.head * 2 > this.q.length) {
    this.q = this.q.slice(this.head)
    this.head = 0
  }
  return this.q.length - this.head
}

/**
 * Your RecentCounter object will be instantiated and called as such:
 * var obj = new RecentCounter()
 * var param_1 = obj.ping(t)
 */

// 可选压缩：防止 head 过大导致数组增长
// if (this.head > 1024 && this.head * 2 > this.q.length) {
//   this.q = this.q.slice(this.head) // 只保留有效部分
//   this.head = 0 // 重置头指针
// }

// 压缩条件：是一个经验性优化条件，可根据实际的优化效果自行调控。
// 目的是在 head 指针过大时，释放掉数组前部的无效空间，防止内存无限增长。

// 第一个条件：this.head > 1024
// 当 head 指针超过 1024 时才考虑压缩
// 这是为了避免频繁压缩带来的性能开销
// 1024 是一个经验值，可以调整

// 第二个条件：this.head * 2 > this.q.length
// 已过期的数据量 > 当前有效数据量
// 无效空间 > 有效空间

// 示例：
// 假设：head = 1200，q.length = 1500，已过期数据：1200个，有效数据：300 个
// 条件 1：head > 1024 ✔️
// 条件 2：head * 2 = 2400 > 1500 ✔️
// 压缩有意义：无效数据比有效数据多

// 压缩前：[过期, 过期, ..., 过期, 有效, 有效, ...]
// 压缩后：[有效, 有效, ...]

// 为什么需要这个优化？
// 没有压缩的情况：
//   时间推移后：
//   q = [t1, t2, t3, ..., t10000]  // 长度 10000
//   head = 9500                    // 只有最后 500 个有效
//   内存浪费：存储了 9500 个过期数据
// 压缩后：
//   q = [t9501, t9502, ..., t10000]  // 长度 500
//   head = 0
//   内存节省：只存储有效数据

// 这个优化是空间换时间的平衡：
// - 不压缩：内存可能无限增长，但操作快
// - 压缩：内存优化，但slice()有O(n)的时间成本
// - 条件判断确保只在真正需要时才压缩
// 这是一个很实用的设计，在数据流处理中很常见，既保证了性能，又防止了内存泄漏。

// ⚠️ 注意：
// 在 leetcode 中提交时，将【可选压缩】部分的代码注释掉也能通过所有测试，并且执行时间和内存消耗都更低。
// 【可选压缩】的逻辑在 leetcode 这道题的测试用例中，并没有体现出啥明显的优势，反而因为 slice() 的开销导致整体性能下降。

// 2025.12.28 提交测试结果记录：
// 有【可选压缩】
//   执行用时分布 40ms 击败 63.57%
//   消耗内存分布 71.29MB 击败 13.18%
// 无【可选压缩】
//   执行用时分布 34ms 击败 82.95%
//   消耗内存分布 69.88MB 击败 54.26%
  • 时间复杂度：O(1)（均摊），每个请求最多入队一次、出队一次
  • 空间复杂度：O(n)，存储最近 3000ms 内的请求

算法思路：

  • 维护队列与头指针，入队新时间 t，同时前移头指针剔除过期（小于 t-3000）的请求
  • 返回队列长度减去头指针位置，即有效请求数量
  • 用头指针替代 shift()，避免数组前移的 O(n) 开销

3. 🎯 s.2 - 二分下界（lower_bound） ​

js
// 二分下界：在有序时间戳数组中查找 >= t-3000 的首位置
var RecentCounter = function () {
  this.times = []
}

/**
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function (t) {
  this.times.push(t)
  const target = t - 3000
  let l = 0,
    r = this.times.length - 1
  while (l <= r) {
    const mid = l + ((r - l) >> 1)
    if (this.times[mid] < target) l = mid + 1
    else r = mid - 1
  }
  return this.times.length - l
}

/**
 * Your RecentCounter object will be instantiated and called as such:
 * var obj = new RecentCounter()
 * var param_1 = obj.ping(t)
 */

// 2025.12.28 提交测试结果记录：
//   执行用时分布 29ms 击败 98.06%
//   消耗内存分布 70.02MB 击败 27.91%
  • 时间复杂度：O(log⁡n)，每次用二分查找首个不小于 t-3000 的位置
  • 空间复杂度：O(n)，存储所有请求时间

算法思路：

  • 维护递增时间数组（t 严格递增）
  • 对 t-3000 做二分下界，返回尾部元素数量 len - idx 作为答案

Discussions